package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/diameter-of-binary-tree/">二叉树的直径(Diameter of Binary Tree)</a>
 * <p>给你一棵二叉树的根节点，返回该树的 直径 。</p>
 * <p>二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。</p>
 * <p>两节点之间路径的 长度 由它们之间边数表示。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,2,3,4,5]
 *                  1
 *                 / \
 *                2   3
 *               / \
 *              4   5
 *      输出：3
 *      解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
 *
 * 示例 2：
 *      输入：root = [1,2]
 *                  1
 *                 /
 *                2
 *      输出：1
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数目在范围 [1, 10^4] 内</li>
 *     <li>-100 <= Node.val <= 100</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/23 9:36
 */
public class LC0543DiameterOfBinaryTree_S {

    static class Solution {
        int maxDiameter = 0;

        public int diameterOfBinaryTree(TreeNode root) {
            dfs(root);
            return maxDiameter;
        }

        public int dfs(TreeNode node) {
            if (node == null) {
                return 0;
            }
            // 左子树的最大直径
            int leftMaxDiameter = dfs(node.left);
            // 右子树的最大直径
            int rightMaxDiameter = dfs(node.right);
            maxDiameter = Math.max(maxDiameter, leftMaxDiameter + rightMaxDiameter);
            // 当前节点的最大直径，Math.max(左子树的最大直径,右子树的最大直径) + 根节点
            return Math.max(leftMaxDiameter, rightMaxDiameter) + 1;
        }
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        Solution solution = new Solution();
        System.out.println(solution.diameterOfBinaryTree(root));
    }
}
